4463. Поход в кино

Чип и Дейл помогают всем в стране iLandia. Как-то после удачного завершения своих миссий они решили сходить в кино. Но тут их поджидала неожиданность! В стране есть только 1 кинотеатр, который находится в столице. Чип завершил свои приключения в городе x, а Дейл в городе y. До начала сеанса осталось мало времени, поэтому оба решили заказать такси, чтобы успеть к началу сеанса. Так как гонорары наших героев небольшие, то каждый желает потратить на такси как можно меньше денег. Чип может подсесть в такси к Дейлу и наоборот, если они оказались в одном городе. Так как у таксистов iLandии постоянная такса за километр, то затраты на путь, который они проехали вдвоем, делят на 2. Вам задано несколько сценариев завершения приключений Чипа и Дейла в разных городах. Для каждого сценария нужно посчитать минимальные вознаграждения героев, чтобы они смогли попасть в кино.

Между двумя произвольными городами существует только одна дорога, по которой между ними можно проехать. Расстояние между любыми двумя соседними городами (между которыми существует прямая дорога) составляет 1 километр. Столица всегда имеет номер 1.

Вход. В первой строке находится два натуральных числа: количество городов n (1 ≤ n ≤ 10⁵) в iLandia, и цена Price (1 ≤ Price ≤ 10⁴) за 1 км в стране. Каждая из следующих n – 1 строк содержит 2 натуральных числа x и y (1 ≤ x, y ≤ n), описывающих наличие дороги из города x в город y. Все дороги двухсторонние. В следующей строке задается количество сценариев q (1 ≤ q ≤ 10⁵). Каждый сценарий начинается с новой строки и задаётся номерами городов c и d (1 ≤ c, d ≤ n), в которых заканчивают свои приключения соответственно Чип и Дейл.

Выход. Выведите два числа: затраты Чипа и Дейла на дорогу с точностью не менее 10^-5.

Пример входа	Пример выхода
3 2 1 2 1 3 3 2 3 1 2 1 3	2 2 0 2 0 2

РЕШЕНИЕ

структуры данных – Least Common Ancestor

Анализ алгоритма

Поскольку между двумя произвольными городами существует только одна дорога, то структура страны представляет собой дерево. Для минимизации общих затрат Чипу и Дейлу необходимо встретиться как можно раньше. Это возможно, если они встретятся в ближайшем общем предке, откуда вместе на такси отправятся в кинотеатр.

Реализация алгоритма

Объявим глобальные массивы для запуска LCA методом двоичного подъема. Граф храним в виде списка смежности в массиве g.

#define MAX 100010

#define LOGMAX 18

vector<int> g[MAX];

int timer, d[MAX], f[MAX], dist[MAX];

int up[MAX][LOGMAX];

Запускаем поиск в глубину из вершины v. Предком v является p. Расстояние до вершины v из столицы (вершины номер 1) равно len. Его сохраняем в ячейке dist[v]. Вычисляем метки d и f.

void dfs (int v, int p = 1, int len = 0)

{

int i, to;

d[v] = timer++;

up[v][0] = p; dist[v] = len;

for(i = 1; i <= l; i++)

up[v][i] = up[up[v][i-1]][i-1];

Просматриваем, куда можно пойти из вершины v. Идем по ребру дерева (v, to).

for(i = 0; i < g[v].size(); i++)

{

to = g[v][i];

if (to != p) dfs (to, v, len + 1);

}

f[v] = timer++;

}

Функция Parent возвращает истину, если a является предком b.

int Parent(int a, int b)

{

return (d[a] <= d[b]) && (f[a] >= f[b]);

}

Вычисление ближайшего общего предка методом двоичного подъема, используя массив up.

int LCA (int a, int b)

{

if (Parent(a, b)) return a;

if (Parent(b, a)) return b;

for (int i = l; i >= 0; i--)

if (!Parent(up[a][i], b)) a = up[a][i];

return up[a][0];

}

Основная часть программы. Читаем входные данные. Вычисляем l = . Строим неориентированный граф, который по условию задачи является деревом.

scanf("%d %d",&n,&Price);

l = 1;

while ((1 << l) <= n) l++;

for(i = 0; i < n - 1; i++)

{

scanf("%d %d",&x,&y);

g[x].push_back(y);

g[y].push_back(x);

}

Запускаем поиск в глубину из столицы, в которой находится кинотеатр.

dfs(1);

Обрабатываем q запрсов.

scanf("%d",&q);

for(i = 0; i < q; i++)

{

scanf("%d %d",&x,&y);

lca = LCA(x, y);

Чип до встречи проедет dist[x] – dist[lca] км, а Дейл dist[y] – dist[lca] км. Вместе на машине они проедут в точности dist[lca] км. Вычисляем и выводим ответ.

Chip = dist[x] - dist[lca];

Deil = dist[y] - dist[lca];

printf("%.5lf %.5lf\n", (Chip + dist[lca] / 2.0) * Price,

(Deil + dist[lca] / 2.0) * Price);

}